package com.gaogzhen.algorithms4.foundation;


/**
 *
 */

public class UF extends AbstractUnionFind{

    /**
     * 触点为根节点树高度
     */
    private byte[] rank;


    /**
     * 初始化
     *
     * @param  n 数量
     */
    public UF(int n) {
        super(n);
        rank = new byte[n];
        for (int i = 0; i < n; i++) {
            rank[i] = 0;
        }
    }

    /**
     * 返回触点p所在分量的树的根节点
     *
     * @param  p 节点p
     * @return 节点p所在树根节点
     */
    @Override
    public int find(int p) {
        validate(p);
        while (p != getId(p)) {
            // 路径减半压缩，当前节点指向其祖父节点
            setId(p , getId(getId(p)));
            p =  getId(p);
        }
        return p;
    }

    /**
     * 归并触点p和触点q
     *
     * @param  p 触点p
     * @param  q 触点q
     */
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;

        // 较低高度的树链接到较高高度的树
        if      (rank[rootP] < rank[rootQ]) setId(rootP, rootQ);
        else if (rank[rootP] > rank[rootQ]) setId(rootQ, rootP);
        else {
            // 高度相同，一个链接到另外一个，被链接的高度+1
            setId(rootQ, rootP);
            rank[rootP]++;
        }
        decreaseCount();
    }
}